package number_647;

public class Solution {
    //中心扩散法；
    public int countSubstrings(String s) {
        int cnt = s.length();
        for (int i = 0; i < s.length(); i++) {
            int prev = i - 1;
            int back = i + 1;
            while (prev >= 0 && back < s.length() && s.charAt(prev) == s.charAt(back)) {
                cnt++;
                prev--;
                back++;
            }
            int curr = i;
            back = i + 1;
            while (curr >= 0 && back < s.length() && s.charAt(curr) == s.charAt(back)) {
                cnt++;
                curr--;
                back++;
            }
        }
        return cnt;
    }

    //dp;
    public int countSubstrings2(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        int res = 0;
        for (int j = 0; j < s.length(); j++) {
            for (int i = j; i >= 0; i--) {
                if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    res++;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        new Solution().countSubstrings("aaa");
    }
}
